Relatório Parcial¶

Otimização de agendamento de filmes¶

Por João Zsigmond

Definição do Problema¶

A partir de uma lista de filmes categorizados, como podemos maximizar o número de filmes assistidos e o tempo assistindo filmes, respeitando os limites de cada categoria.

  • Apenas um filme pode ser assistido por vez.
  • O limite de número máximo de filmes assistido por categoria tem que ser respeitado.

Input¶

Recebemos como entrada uma lista de filmes definidos por:

  1. horário de início
  2. horário de término
  3. categoria

E também recebemos o limite de filmes que podem ser assistidos por categoria.

A Heurística Gulosa¶

A heurística gulosa, em termos gerais, ordena os filmes por ordem crescente com relação ao horário de término e seleciona sempre o próximo filme na lista. Se o próximo filme na lista não pode ser assistido pois não se enquadra nas regras, ele é pulado. Um filme não se encaixa nas regras quando 1. já alcancamos o limite de filmes que podem ser assistidos em sua categoria ou 2. o filme tem início antes que o último filme chegou ao fim, dessa forma, se o assistirmos estaríamos assistindo dois filmes simultanteamente.

Código fonte da heurística gulosa¶

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;

// Define a struct to represent a movie
struct Movie {
    int start_time;
    int end_time;
    int category;
};

int main() {
    // Start the timer
    auto startTime = chrono::steady_clock::now();

    int num_movies, num_categories;
    cin >> num_movies >> num_categories;

    // Read the category limits into a vector
    vector<int> category_limit(num_categories + 1);
    for (int i = 1; i <= num_categories; i++) {
        cin >> category_limit[i];
    }

    // Read the movie information into a vector
    vector<Movie> movies(num_movies);
    for (int i = 0; i < num_movies; i++) {
        cin >> movies[i].start_time >> movies[i].end_time >> movies[i].category;
        if (movies[i].end_time < movies[i].start_time) {
            movies[i].end_time = 24;
        }

        if (movies[i].end_time == movies[i].start_time) {
            movies[i].end_time += 1;
        }
    }

    // Sort the movies by end time
    sort(movies.begin(), movies.end(), [](const Movie& a, const Movie& b) {
        if (a.end_time == b.end_time) { return a.start_time < b.start_time; }
        return a.end_time < b.end_time;
    });

    // // Sort the movies by start time
    // sort(movies.begin(), movies.end(), [](const Movie& a, const Movie& b) {
    //     return a.start_time < b.start_time;
    // });

    // Define a bitset to represent the availability of each hour of the day
    bitset<24> hours;

    // Keep track of how many movies of each category have been watched
    vector<int> num_watched(num_categories + 1, 0);

    // Keep track of the indices of the watched movies
    vector<int> watched;

    int time_watched = 0;

    // Iterate over the movies and check if each movie can be watched
    for (int i = 0; i < num_movies; i++) {
        const Movie& movie = movies[i];

        // Check if any hour of the movie overlaps with an already watched movie
        bool can_watch = true;
        for (int hour = movie.start_time; hour < movie.end_time; hour++) {
            if (hours[hour]) {
                can_watch = false;
                break;
            }
        }
        if (hours[movie.start_time]) { can_watch = false; }

        // If the movie can be watched and its category limit has not been reached,
        // mark the hours as watched, add the movie to the list of watched movies,
        // and print the start time, end time, and category of the movie
        if (can_watch && num_watched[movie.category] < category_limit[movie.category]) {
            num_watched[movie.category]++;
            time_watched += movie.end_time - movie.start_time;
            watched.push_back(i);
            hours[movie.start_time] = true;
            for (int hour = movie.start_time; hour < movie.end_time; hour++) {
                hours[hour] = true;
            }
            cout << movie.start_time << " " << movie.end_time << " " << movie.category << endl;
        }
    }

    // Output the number of watched movies
    cout << "\nNúmero de filmes: " << watched.size() << endl;
    cout << "Tempo de tela (em horas): " << time_watched << endl;

    // Calculate the time elapsed during algorithm execution
    auto endTime = chrono::steady_clock::now();
    double duration = chrono::duration_cast<chrono::microseconds>(endTime - startTime).count();

    cout << fixed;
    cout << "Time elapsed during the greedy algorithm (in microseconds): " << duration << endl;
    cout << scientific;

    return 0;
}

Explicação do código fonte da heurística gulosa¶

  1. Tratamento do input

Sempre começamos tratando os dados do input. Recebemos como entrada do nosso programa um arquivo na seguinte estrutura: primeira linha contem dois números, o número total de filmes e o número total de categorias. A segunda linha possui os limites de cada categoria. As linhas seguintes definem os filmes. Cada uma delas possuem 3 números, horário de início, horário de término e categoria. Começamos montando uma estrutura de dados para representar cada filme. Depois, transformamos os limites de cada categoria em um vetor e os filmes em um vetor de filmes.

  1. Ordenação

O segundo passo é ordenar o vetor de filmes por horário de término.

  1. Uso do bitset

Usamos um bitset para organizar quais horas do dia estão livres para assisitirmos um filme. Sempre que um novo filme é assistido, preenchemos o bitset nos horários que o filme nos ocupou.

  1. Validação do filme seguinte

Fazemos um loop no vetor de filmes e vamos assistindo um em seguida do outro. Sempre, antes de assistir um filme temos que verificar se podemos o assistir de acordo com as regras impostas pelo desafio. Pra isso, quando nos deparamos com um novo filme, primeiro checamos se os horários que ele ocupa não está sendo ocupado por nenhum outro filme que ja assistimos. Depois checamos se ja alcancamos o limite de sua categoria. Se essas duas regras não forem quebradas, assistimos o filme e atualizamos o vetor de filmes assistidos, os horários ocupados por esse filme e adicionamos 1 no vetor que toma conta dos limites de categoria.

A Heurística Aleatória¶

Diferente do que o nome sugere, a nossa heurística aleatória na verdade é apenas um pouco aleatória.

A heurística aleatória segue as mesmas regras da heurística gulosa, porém com uma diferenciação. 25% das vezes, ao invés de seguir a lista ordenada de filmes, o algoritimo que segue a heurística aleatória irá selecionar um filme qualquer que ainda não tenha sido assistido e que não quebre nenhuma das regras do desafio.

A aleatoriedade é interessante pois a heurística puramente gulosa pode se prender em um ótimo local. Se de vez em quando o algorítimo é induzido a selecionar um filme aleatório, ele pode sair do ótimo local.

Código fonte da heurística aleatória¶

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;

// Define a struct to represent a movie
struct Movie {
    int start_time;
    int end_time;
    int category;
};

bool check_can_watch(const Movie& movie, const bitset<24>& hours, const vector<int>& num_watched, const vector<int>& category_limit) {
    if (num_watched[movie.category] >= category_limit[movie.category]) { return false; }
    for (int hour = movie.start_time; hour < movie.end_time; hour++) {
        if (hours[hour]) {
            return false;
        }
    }
    if (hours[movie.start_time]) { return false; }
    return true;
}

int main() {
    // Start the timer
    auto startTime = chrono::steady_clock::now();

    srand((unsigned) time(NULL));
    int num_movies, num_categories;
    cin >> num_movies >> num_categories;

    // Read the category limits into a vector
    vector<int> category_limit(num_categories + 1);
    for (int i = 1; i <= num_categories; i++) {
        cin >> category_limit[i];
    }

    // Read the movie information into a vector
    vector<Movie> unwatched_movies(num_movies);
    for (int i = 0; i < num_movies; i++) {
        cin >> unwatched_movies[i].start_time >> unwatched_movies[i].end_time >> unwatched_movies[i].category;
        if (unwatched_movies[i].end_time < unwatched_movies[i].start_time) {
            unwatched_movies[i].end_time = 24;
        }

        if (unwatched_movies[i].end_time == unwatched_movies[i].start_time) {
            unwatched_movies[i].end_time += 1;
        }
    }

    vector<Movie> watched_movies;
    vector<Movie> lost_movies;

    // Sort the movies by end time
    sort(unwatched_movies.begin(), unwatched_movies.end(), [](const Movie& a, const Movie& b) {
        if (a.end_time == b.end_time) { return a.start_time < b.start_time; }
        return a.end_time < b.end_time;
    });

    // Define a bitset to represent the availability of each hour of the day
    bitset<24> hours;

    // Keep track of how many movies of each category have been watched
    vector<int> num_watched(num_categories + 1, 0);

    int time_watched = 0;

    // Iterate over the movies and check if each movie can be watched
    while (!unwatched_movies.empty()) {
        bool end = false;
        Movie movie;
        int index;
        int random_num = rand() % 4;
        if (random_num != 0) {
            index = 0;
            movie = unwatched_movies.front();
        } else {
            index = rand() % unwatched_movies.size();
            movie = unwatched_movies[index];

            while(!check_can_watch(movie, hours, num_watched, category_limit)) {
                lost_movies.push_back(movie);
                unwatched_movies.erase(unwatched_movies.begin() + index);

                if (unwatched_movies.empty()) { end = true; break; }

                index = rand() % unwatched_movies.size();
                movie = unwatched_movies[index];
            }
        }

        if (end) { break; }

        if (check_can_watch(movie, hours, num_watched, category_limit)) {
            hours[movie.start_time] = true;
            for (int hour = movie.start_time; hour < movie.end_time; hour++) {
                hours[hour] = true;
            }
            num_watched[movie.category]++;
            time_watched += movie.end_time - movie.start_time;
            watched_movies.push_back(movie);
            unwatched_movies.erase(unwatched_movies.begin()+index);
            cout << movie.start_time << " " << movie.end_time << " " << movie.category << endl;
        } else {
            lost_movies.push_back(movie);
            unwatched_movies.erase(unwatched_movies.begin() + index);
        }
    }

    // Output the number of watched movies
    cout << "\nNúmero de filmes: " << watched_movies.size() << endl;
    cout << "Tempo de tela (em horas): " << time_watched << endl;

    // Calculate the time elapsed during algorithm execution
    auto endTime = chrono::steady_clock::now();
    double duration = chrono::duration_cast<chrono::microseconds>(endTime - startTime).count();

    cout << fixed;
    cout << "Time elapsed during the stochastic greedy algorithm (in microseconds): " << duration << endl;
    cout << scientific;

    return 0;
}

Explicação da heurística¶

  1. Tratamento do input

Sempre começamos tratando os dados do input. Recebemos como entrada do nosso programa um arquivo na seguinte estrutura: primeira linha contem dois números, o número total de filmes e o número total de categorias. A segunda linha possui os limites de cada categoria. As linhas seguintes definem os filmes. Cada uma delas possuem 3 números, horário de início, horário de término e categoria. Começamos montando uma estrutura de dados para representar cada filme. Depois, transformamos os limites de cada categoria em um vetor e os filmes em um vetor de filmes.

  1. Ordenação

O segundo passo é ordenar o vetor de filmes por horário de término.

  1. Uso do bitset

Usamos um bitset para organizar quais horas do dia estão livres para assisitirmos um filme. Sempre que um novo filme é assistido, preenchemos o bitset nos horários que o filme nos ocupou.

  1. Validação do filme seguinte

Essa etapa, na heurística aleatória, é diferente da heurística gulosa. Em 75% das vezes vamos seguir o mesmo procedimento da heurística gulosa, porém em 25% das vezes, iremos assistir um filme aleatório da lista que ainda não foi assistido e se encaixa nas regras do desafio.

Profiling com Valgrind¶

Profiling da heurística gulosa¶

-- line 7 ----------------------------------------
     .
     .           // Define a struct to represent a movie
     .           struct Movie {
     .               int start_time;
     .               int end_time;
     .               int category;
     .           };
     .
    11 ( 0.00%)  int main() {
     .               int num_movies, num_categories;
     6 ( 0.00%)      cin >> num_movies >> num_categories;
 8,589 ( 0.14%)  => ???:0x0000000000109150 (2x)
     .
     .               // Read the category limits into a vector
     3 ( 0.00%)      vector<int> category_limit(num_categories + 1);
    45 ( 0.00%)      for (int i = 1; i <= num_categories; i++) {
    32 ( 0.00%)          cin >> category_limit[i];
10,442 ( 0.18%)  => ???:0x0000000000109150 (10x)
     .               }
     .
     .               // Read the movie information into a vector
     1 ( 0.00%)      vector<Movie> movies(num_movies);
 4,006 ( 0.07%)      for (int i = 0; i < num_movies; i++) {
 9,002 ( 0.15%)          cin >> movies[i].start_time >> movies[i].end_time >> movies[i].category;
3,292,381 (55.46%)  => ???:0x0000000000109150 (3,000x)
 3,000 ( 0.05%)          if (movies[i].end_time < movies[i].start_time) {
   135 ( 0.00%)              movies[i].end_time = 24;
     .                   }
     .               }
     .
     .               // Sort the movies by end time
     .               sort(movies.begin(), movies.end(), [](const Movie& a, const Movie& b) {
24,984 ( 0.42%)          if (a.end_time == b.end_time) { return a.start_time < b.start_time; }
19,774 ( 0.33%)          return a.end_time < b.end_time;
     .               });
     .
     .               // // Sort the movies by start time
     .               // sort(movies.begin(), movies.end(), [](const Movie& a, const Movie& b) {
     .               //     return a.start_time < b.start_time;
     .               // });
     .
     .               // Define a bitset to represent the availability of each hour of the day
     1 ( 0.00%)      bitset<24> hours;
     .
     .               // Keep track of how many movies of each category have been watched
     3 ( 0.00%)      vector<int> num_watched(num_categories + 1, 0);
     .
     .               // Keep track of the indices of the watched movies
     .               vector<int> watched;
     .
     .               // Iterate over the movies and check if each movie can be watched
 4,007 ( 0.07%)      for (int i = 0; i < num_movies; i++) {
 1,000 ( 0.02%)          const Movie& movie = movies[i];
     .
     .                   // Check if any hour of the movie overlaps with an already watched movie
     .                   bool can_watch = true;
 7,075 ( 0.12%)          for (int hour = movie.start_time; hour < movie.end_time; hour++) {
 2,963 ( 0.05%)              if (hours[hour]) {
     .                           can_watch = false;
     .                           break;
     .                       }
     .                   }
    25 ( 0.00%)          if (hours[movie.start_time]) { can_watch = false; }
     .
     .                   // If the movie can be watched and its category limit has not been reached,
     .                   // mark the hours as watched, add the movie to the list of watched movies,
     .                   // and print the start time, end time, and category of the movie
   108 ( 0.00%)          if (can_watch && num_watched[movie.category] < category_limit[movie.category]) {
    40 ( 0.00%)              num_watched[movie.category]++;
     .                       watched.push_back(i);
    20 ( 0.00%)              hours[movie.start_time] = true;
   137 ( 0.00%)              for (int hour = movie.start_time; hour < movie.end_time; hour++) {
     .                           hours[hour] = true;
     .                       }
   180 ( 0.00%)              cout << movie.start_time << " " << movie.end_time << " " << movie.category << endl;
31,724 ( 0.53%)  => ???:0x00000000001091e0 (60x)
     .                   }
     .               }
     .
     .               // Output the number of watched movies
     .               // cout << watched.size() << endl;
     .
     .               return 0;
    15 ( 0.00%)  }

Profiling da heurística aleatória¶

-- line 8 ----------------------------------------
     .           // Define a struct to represent a movie
     .           struct Movie {
     .               int start_time;
     .               int end_time;
     .               int category;
     .           };
     .
     .           bool check_can_watch(const Movie& movie, const bitset<24>& hours, const vector<int>& num_watched, const vector<int>& category_limit) {
 4,121 ( 0.05%)      if (num_watched[movie.category] >= category_limit[movie.category]) { return false; }
 7,200 ( 0.09%)      for (int hour = movie.start_time; hour < movie.end_time; hour++) {
 1,756 ( 0.02%)          if (hours[hour]) {
     .                       return false;
     .                   }
     .               }
    16 ( 0.00%)      if (hours[movie.start_time]) { return false; }
     .               return true;
     .           }
     .
    11 ( 0.00%)  int main() {
     4 ( 0.00%)      srand((unsigned) time(NULL));
 6,817 ( 0.08%)  => ???:0x0000000000109220 (1x)
     8 ( 0.00%)  => ???:0x0000000000109200 (1x)
     .               int num_movies, num_categories;
     6 ( 0.00%)      cin >> num_movies >> num_categories;
 8,589 ( 0.10%)  => ???:0x00000000001091c0 (2x)
     .
     .               // Read the category limits into a vector
     3 ( 0.00%)      vector<int> category_limit(num_categories + 1);
    45 ( 0.00%)      for (int i = 1; i <= num_categories; i++) {
    32 ( 0.00%)          cin >> category_limit[i];
10,442 ( 0.13%)  => ???:0x00000000001091c0 (10x)
     .               }
     .
     .               // Read the movie information into a vector
     6 ( 0.00%)      vector<Movie> unwatched_movies(num_movies);
 1,750 ( 0.02%)  => /usr/include/c++/9/bits/stl_vector.h:std::vector<Movie, std::allocator<Movie> >::vector(unsigned long, std::allocator<Movie> const&) (1x)
 4,006 ( 0.05%)      for (int i = 0; i < num_movies; i++) {
 9,002 ( 0.11%)          cin >> unwatched_movies[i].start_time >> unwatched_movies[i].end_time >> unwatched_movies[i].category;
3,292,381 (40.23%)  => ???:0x00000000001091c0 (3,000x)
 4,000 ( 0.05%)          if (unwatched_movies[i].end_time < unwatched_movies[i].start_time) {
   135 ( 0.00%)              unwatched_movies[i].end_time = 24;
     .                   }
     .               }
     .
     7 ( 0.00%)      vector<Movie> watched_movies(num_movies);
 1,750 ( 0.02%)  => /usr/include/c++/9/bits/stl_vector.h:std::vector<Movie, std::allocator<Movie> >::vector(unsigned long, std::allocator<Movie> const&) (1x)
     6 ( 0.00%)      vector<Movie> lost_movies(num_movies);
 1,750 ( 0.02%)  => /usr/include/c++/9/bits/stl_vector.h:std::vector<Movie, std::allocator<Movie> >::vector(unsigned long, std::allocator<Movie> const&) (1x)
     .
     .               // Sort the movies by end time
     .               sort(unwatched_movies.begin(), unwatched_movies.end(), [](const Movie& a, const Movie& b) {
24,984 ( 0.31%)          if (a.end_time == b.end_time) { return a.start_time < b.start_time; }
19,774 ( 0.24%)          return a.end_time < b.end_time;
     .               });
     .
     .               // Define a bitset to represent the availability of each hour of the day
     2 ( 0.00%)      bitset<24> hours;
     .
     .               // Keep track of how many movies of each category have been watched
     3 ( 0.00%)      vector<int> num_watched(num_categories + 1, 0);
     .
     .               // Keep track of the indices of the watched movies
     .               vector<int> watched;
     .
     .               // Iterate over the movies and check if each movie can be watched
    79 ( 0.00%)      while (!unwatched_movies.empty()) {
     .                   bool end = false;
     .                   Movie movie;
     .                   int index;
    39 ( 0.00%)          int random_num = rand() % 4;
 2,406 ( 0.03%)  => ???:0x0000000000109190 (39x)
    78 ( 0.00%)          if (random_num != 0) {
    26 ( 0.00%)              index = 0;
   130 ( 0.00%)              movie = unwatched_movies.front();
     .                   } else {
    91 ( 0.00%)              index = rand() % unwatched_movies.size();
   806 ( 0.01%)  => ???:0x0000000000109190 (13x)
   104 ( 0.00%)              movie = unwatched_movies[index];
     .
   961 ( 0.01%)              while(!check_can_watch(movie, hours, num_watched, category_limit)) {
     .                           lost_movies.push_back(movie);
     .                           unwatched_movies.erase(unwatched_movies.begin() + index);
     .
 1,925 ( 0.02%)                  if (unwatched_movies.empty()) { end = true; break; }
     .
 5,766 ( 0.07%)                  index = rand() % unwatched_movies.size();
59,466 ( 0.73%)  => ???:0x0000000000109190 (961x)
 6,727 ( 0.08%)                  movie = unwatched_movies[index];
     .                       }
     .                   }
     .
     .                   if (end) { break; }
     .
     .                   if (check_can_watch(movie, hours, num_watched, category_limit)) {
     .                       hours[movie.start_time] = true;
    92 ( 0.00%)              for (int hour = movie.start_time; hour < movie.end_time; hour++) {
     .                           hours[hour] = true;
     .                       }
    28 ( 0.00%)              num_watched[movie.category]++;
     .                       watched_movies.push_back(movie);
     .                       unwatched_movies.erase(unwatched_movies.begin()+index);
   168 ( 0.00%)              cout << movie.start_time << " " << movie.end_time << " " << movie.category << endl;
24,477 ( 0.30%)  => ???:0x00000000001092a0 (42x)
     .                   } else {
     .                       lost_movies.push_back(movie);
     .                       unwatched_movies.erase(unwatched_movies.begin() + index);
     .                   }
     .               }
     .
     .               // Output the number of watched movies
     .               // cout << watched.size() << endl;
     .
     .               return 0;
    15 ( 0.00%)  }

Conclusões sobre o profiling¶

Podemos notar que as instruções de ler dados de um arquivo e de escrever dados para o stdout são as instruções que mais consomem. Além disso, as instruções que involvem calculode variáveis com aleatoriedade também impactam muito.

Comparação de Resultados¶

Visualização comparativa entre a performance da heurística gulosa e aleatória¶

Para criar essas visualizações foram levadas em consideração as seguintes variáveis:

  • Número de filmes assistidos
  • Tempo assistindo filmes
  • Tempo de execução do algoritimo
In [9]:
from os import listdir
from os.path import isfile, join

import pandas as pd
import plotly.graph_objects as go

import plotly.io as pio
pio.renderers.default='notebook'

files = [f for f in listdir("./outputs/greedy") if isfile(join("./outputs/greedy", f))]

num_movies = {}
screen_time = {}
execution_duration = {}

for file_name in files:
    num_movies[file_name] = {}
    screen_time[file_name] = {}
    execution_duration[file_name] = {}
    with open('./outputs/greedy/{}'.format(file_name), 'r') as f:
        lines = f.readlines()
        num_movies[file_name]['greedy'] = int(float(lines[-3].split()[-1]))
        screen_time[file_name]['greedy'] = int(float(lines[-2].split()[-1]))
        execution_duration[file_name]['greedy'] = int(float(lines[-1].split()[-1]))
        
        

    with open('./outputs/random/{}'.format(file_name), 'r') as f:
        lines = f.readlines()
        num_movies[file_name]['random'] = int(float(lines[-3].split()[-1]))
        screen_time[file_name]['random'] = int(float(lines[-2].split()[-1]))
        execution_duration[file_name]['random'] = int(float(lines[-1].split()[-1]))

num_movies_df = pd.DataFrame.from_dict(num_movies, 'index')
screen_time_df = pd.DataFrame.from_dict(screen_time, 'index')
execution_duration_df = pd.DataFrame.from_dict(execution_duration, 'index')
In [10]:
fig = go.Figure()
fig.add_trace(go.Bar(
    x=files,
    y=num_movies_df['greedy'],
    name='Greedy Algorithm',
    marker_color='indianred'
))
fig.add_trace(go.Bar(
    x=files,
    y=num_movies_df['random'],
    name='Stochastic Algorithm',
    marker_color='lightsalmon'
))

fig.update_layout(barmode='group', xaxis_tickangle=-45, title="Number of Movies")
fig.show()
In [11]:
fig = go.Figure()
fig.add_trace(go.Bar(
    x=files,
    y=screen_time_df['greedy'],
    name='Greedy Algorithm',
    marker_color='indianred'
))
fig.add_trace(go.Bar(
    x=files,
    y=screen_time_df['random'],
    name='Stochastic Algorithm',
    marker_color='lightsalmon'
))

fig.update_layout(barmode='group', xaxis_tickangle=-45, title="Total Screen Time")
fig.show()
In [12]:
fig = go.Figure()
fig.add_trace(go.Bar(
    x=files,
    y=execution_duration_df['greedy'],
    name='Greedy Algorithm',
    marker_color='indianred'
))
fig.add_trace(go.Bar(
    x=files,
    y=execution_duration_df['random'],
    name='Stochastic Algorithm',
    marker_color='lightsalmon'
))

fig.update_layout(barmode='group', xaxis_tickangle=-45, title="Execution Duration (microseconds)")
fig.show()

Conclusão dos resultados¶

Analisando os resultados, podemos concluir que a performance da heurística gulosa é melhor do que a performance da heurística aleatória para todas as métricas comparadas.

  • Número de filmes assistidos:

Para todos os inputs, a heurística gulosa assisitiu um número maior ou igual ao número de filmes assistidos pela heurística com aleatoriedade.

  • Tempo de tela:

Para todos os inputs, a heurística gulosa passou mais tempo assistindo filmes ou a mesma quantidade de tempo que a heurística com aleatoriedade

  • Tempo de execução

Para todos os inputs, o tempo de execução da heurística gulosa foi menor do que o tempo de execução da heurística aleatória.